1. Technical Field
The present invention relates generally to an improved graphics subsystem and in particular to a method and an apparatus for processing binary space partitioning (BSP) trees. Still more particularly, the present invention provides a method and an apparatus for improving the accuracy of the bounding volumes for BSP-trees.
2. Description of the Related Art
The display of two and three dimensional graphic images of complex scenes in real time have improved greatly as hardware and software have improved. These images are very complex, so efficient processing is of utmost importance. Binary space partitioning (BSP) trees were introduced in the early 1980""s (See Fuchs, Kedem, and Nayor, xe2x80x9cOn Visible Surface Generation by A Priori Tree Structuresxe2x80x9d, SIGGRAPH ""80, pp. 124-133, the content of which is hereby incorporated by reference for all purposes) to aid in the processing of 3-D scenes.
BSP trees are a standard tool in image processing and are continually being improved through refinement. A BSP tree divides an n-dimensional space into two components using an n-1 dimensional object. For example, a 0 dimensional point on a line divides the 1 dimensional line into two components. Alternatively, a 1 dimensional line divides a 2 dimensional plane into two components. For a 3 dimension scene, a 2 dimensional plane divides the scene into two components.
The process of subdivision continues recursively to subdivide an n-dimensional space into smaller components called polytopes. A polytope is a generalization of a polyhedron. Informally, it is a multi-dimensional solid with flat sides. The faces are the hyper-planes that are subdividing the n-dimensional space. Storing these polytopes in a BSP tree allows the n-dimensional space to be classified and sorted in a manner that assists in carrying out other processing tasks, such as hidden surface removal.
Polytopes can approximate objects in the n-dimensional space. Therefore, it would be advantageous to have improved bounding volumes in a BSP tree to make graphics processing more efficient.
The present invention provides a method, system, and program product for creating a child node of a binary space partitioning (BSP) tree node that better approximates the size of an object to be rendered. In one embodiment, a a binary space partitioning tree is created. A rendering process then determines whether either a top node or a child node in a first level of child nodes is a good approximation of the object to be rendered. If not, then the rendering process modifies the binary space partitioning tree to include a new child node having boundaries that are closer to the maximum coordinates of primitives defining the object than are the boundaries of the top node or of the child nodes in the first level of child nodes. This new child node may have a bounding volume that overlaps the bounding volumes of other child nodes in the BSP tree.